package the01bag;

public class PartitionEqualSubsetSum {
    /**
     * 416. 分割等和子集
     * 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
     *
     * 1 <= nums.length <= 200
     * 1 <= nums[i] <= 100
     */

    public static void main(String[] args) {

    }

    public boolean mySolution(int[] nums) {
        if(nums == null || nums.length == 1)
            return false;

        int sum = 0;
        for(int i : nums){
            sum += i;
        }
        if(sum % 2 != 0) return false;

        int target = sum / 2;
        int[] dp = new int[target + 1];
        // 注意，这里是从后往前推，而且需要对第一行进行遍历，这个过程就相当于初始化了
        // 用二维数组是从第二行开始递推，因此需要手动初始化第一行
        // 开始推导
        for(int i = 0; i < nums.length; i++){
            for(int j = target; j >= nums[i]; j--){
                dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);
            }
            if(dp[target] == target) return true;
        }

        return dp[target] == target;
    }
}
